The present invention relates to the design of a hardware implemented device to perform a "hash" operation in a digital computer. The essential purpose of a hash function is to transform an unknown and possibly skewed distribution of values into a more uniform distribution, often over a smaller range of values. One application of a hash function is in an associative memory. Here, an identifier, such as a person's name or account number, is transformed by a hash function into an address in a computer's memory which is used as a starting point for a search for the data associated with the identifier. For the associative memory to perform efficiently, it is important that the addresses given by the hash functions be spread relatively evenly over the possible addresses, even when the identifiers are highly correlated. There are many other uses of hash functions, including uses in operating systems, compilers, interpreters, data base management, cryptographic schemes, spelling checkers, error correction and detection schemes, etc.
In addition to the above noted uses of a hash function another very important utilization is for the efficient translation of virtual addresses to main storage real addresses by means of a hash index table which contains main storage addresses. A hashing function is provided for generating a uniform distribution of hash index table entry addresses from a nonuniform distribution of virtual addresses in a data processing system, where the size of the hash index table is variable and is based on the size of main storage. If an adequate hashing function is chosen, the hash index table may be kept to a minimum size and used or filled very efficiently.
For a much more detailed description of the use of hashing refer to the following three publications: (1) Donald E. Knuth, "The Art of Computer Programming," Vol. III (Sorting and Searching). Addison-Wesley Publishing Company, Menlo Park, Calif. (1973); (2) Aho, Hopcroft and Ullman, "The Design and Analysis of Computer Algorithms," Addison-Wesley Publishing Company, Menlo Park, Calif. (1974); (3) M. N. Wegman and J. L. Carter, "New Hash Functions and Their Use in Authentication and Set Equality," Journal of Computer and System Sciences, Vol. 22, pp. 265-279 (June 1981).
Hash functions are usually implemented in software (that is, by a computer program), however, according to the teachings of the present invention an extremely versatile circuit is provided to perform the hash operation. There are two significant advantages to making hardware perform hashing: firstly, the hashing operation can be speeded up substantially, and secondly, a significantly more sophisticated hashing procedure or algorithm can be economically used.
A potential disadvantage of performing hashing in hardware is a particular function chosen might perform poorly on a particular set of data.
That is, with a particular distribution of objects to be hashed, poorly distributed hashed output would be realized. Accordingly, in most known prior art systems hardware or fixed hashing has been utilized only where the input data has a more or less known, fixed characteristic. Conversely when more sophisticated hashing is required more complex and time consuming hashing algorithms have been embodied in software with a significant increase in the requisite time for performing such hashing operations.